﻿public class Solution {
    public bool WordBreak(string s, IList<string> wordDict)
    {
        HashSet<string> wordSet = new HashSet<string>(wordDict);

        bool[] dp = new bool[s.Length + 1];
        dp[0] = true;

        for (int i = 1; i <= s.Length; i++)
        {
            for (int j = 0; j < i; j++)
            {
                if (wordSet.Contains(s.Substring(j, i - j)) && dp[j])
                {
                    dp[i] = true;
                }
            }
        }
        return dp[s.Length];
    }

    public static void Main(string[] args)
    {
        string s = "aaaaaaa";
        string[] wordDict = ["aaaa", "aaa"];

        Solution solution = new Solution();
        bool res = solution.WordBreak(s, wordDict);
        Console.WriteLine(res);
    }
}